<!DOCTYPE html>
<html lang="en">
    <head>
  <!-- 元数据 -->
  <meta charset="utf-8">
  <link rel="icon" href="">
  <title>算法设计与分析 | 7att1ce's blog</title>
  <meta name="author" content="7att1ce" />
  <meta http-equiv="Cache-Control" content="no-transform" />
  <meta http-equiv="Cache-Control" content="no-siteapp" />
  <meta http-equiv="X-UA-Compatible" content="IE=edge" />
  <meta name="robots" content="index,follow" />
  <meta name="viewport" content="width=device-width, initial-scale=1, maximum-scale=1" />
  <meta name="format-detection" content="telphone=no, email=no" />
  
    <meta name="keywords" content="" />
  
  <meta name="description" content="1 基础知识1.1 渐进符号 如果$\lim\limits_{n\to\infty}\frac{f(n)}{g(n)}$存在并且等于某个常数$c&gt;0$, 那么$f(n)&#x3D;\Theta(g(n))$ 如果$\lim\limits_{n\to\infty}\frac{f(n)}{g(n)}&#x3D;0$, 那么$f(n)&#x3D;o(g(n))$ 如果$\lim\limits_{n\to\infty}\frac">
<meta property="og:type" content="article">
<meta property="og:title" content="算法设计与分析">
<meta property="og:url" content="http://7att1ce.github.io/2021/03/09/%E7%AE%97%E6%B3%95%E8%AE%BE%E8%AE%A1%E4%B8%8E%E5%88%86%E6%9E%90/index.html">
<meta property="og:site_name" content="7att1ce&#39;s blog">
<meta property="og:description" content="1 基础知识1.1 渐进符号 如果$\lim\limits_{n\to\infty}\frac{f(n)}{g(n)}$存在并且等于某个常数$c&gt;0$, 那么$f(n)&#x3D;\Theta(g(n))$ 如果$\lim\limits_{n\to\infty}\frac{f(n)}{g(n)}&#x3D;0$, 那么$f(n)&#x3D;o(g(n))$ 如果$\lim\limits_{n\to\infty}\frac">
<meta property="og:locale" content="en_US">
<meta property="og:image" content="http://7att1ce.github.io/null">
<meta property="article:published_time" content="2021-03-09T19:24:48.000Z">
<meta property="article:modified_time" content="2021-05-10T17:37:01.581Z">
<meta property="article:author" content="7att1ce">
<meta name="twitter:card" content="summary">
<meta name="twitter:image" content="http://7att1ce.github.io/null">
<meta name="twitter:site" content="@null">
  
  <!-- 站点验证相关 -->
  
    
    
    
  
  <!-- 样式表文件 -->
  <link rel="stylesheet" id="kratos-css" href="/css/kratosr.min.css" type="text/css" media="all">
  
    <link rel="stylesheet" id="highlight-css" href="/css/highlight/night-eighties.min.css" type="text/css" media="all">
  
  
  <link rel="stylesheet" id="fontawe-css" href="https://cdn.jsdelivr.net/npm/font-awesome@4.7.0/css/font-awesome.min.css" type="text/css" media="all">
  <link rel="stylesheet" id="nprogress-css" href="https://cdn.jsdelivr.net/npm/nprogress@0.2.0/nprogress.min.css" type="text/css" media="all">
  
  
    <link rel="stylesheet" href="https://cdn.jsdelivr.net/npm/aplayer@1.10.1/dist/APlayer.min.css">
  
  
    <link rel="stylesheet" href="https://cdn.jsdelivr.net/gh/fancyapps/fancybox@3.5.7/dist/jquery.fancybox.min.css">
  
  
    <link rel="stylesheet" id="darkmode-css" href="/css/kr-dark.min.css" type="text/css" media="all">
  
  <!-- 不得不预先加载的一些JS文件 -->
  <script src="https://cdn.jsdelivr.net/npm/jquery@3.6.0/dist/jquery.min.js"></script>
  
    <script src="https://cdn.jsdelivr.net/npm/qrcode_js@1.0.0/qrcode.min.js"></script>
  
<meta name="generator" content="Hexo 5.4.0"></head>


    <body class="custom-background">
        <div id="kratos-wrapper">
    <div id="kratos-page">
        <div id="kratos-header">
            <header id="kratos-desktop-topnav" class="kratos-topnav">
                <div class="container">
                    <div class="nav-header">
                        <nav id="kratos-menu-wrap">
                            <ul id="kratos-primary-menu" class="sf-menu">
                                
                                    
                                        <li><a href="/"><i class="fa fa-home"></i>首页</a></li>
                                    
                                
                                    
                                        <li><a href="/archives/"><i class="fa fa-file"></i>档案馆</a></li>
                                    
                                
                                    
                                        <li><a href="/friends/"><i class="fa fa-paw"></i>好伙伴</a></li>
                                    
                                
                                    
                                        <li>
                                            <a><i class="fa fa-link"></i>链接</a>
                                            <ul class="sub-menu">
                                                
                                                    
                                                
                                                    
                                                        <li><a target="_blank" rel="noopener" href="https://candinya.com">作者博客</a></li>
                                                    
                                                
                                                    
                                                        <li><a target="_blank" rel="noopener" href="https://github.com/Candinya/Kratos-Rebirth">项目链接</a></li>
                                                    
                                                
                                            </ul>
                                        </li>
                                    
                                
                            </ul>
                        </nav>
                    </div>
                </div>
            </header>
            <header id="kratos-mobile-topnav" class="kratos-topnav">
                <div class="container">
                    <div class="color-logo"><a href="/">7att1ce&#39;s blog</a></div>
                    <div class="nav-toggle">
                        <a class="kratos-nav-toggle js-kratos-nav-toggle">
                            <i></i>
                        </a>
                    </div>
                </div>
            </header>
        </div>
        <div class="kratos-start kratos-hero-2">
            <!-- <div class="kratos-overlay"></div> -->
            <div class="kratos-cover kratos-cover-2 text-center">
                <div class="desc desc2 animate-box">
                    <a href="/">
                        <h2>7att1ce&#39;s blog</h2> <br />
                        <span></span>
                    </a>
                </div>
            </div>
        </div>

        <div id="kratos-blog-post">
            <div class="container">
                <div id="main" class="row">
                    

        <section class="col-md-8">
    <article>
        <div class="kratos-hentry kratos-post-inner clearfix">
            <header class="kratos-entry-header">
                <h1 class="kratos-entry-title text-center">算法设计与分析</h1>
                
                <ul class="kratos-post-meta text-center">
                    <li><i class="fa fa-calendar"></i> 2021-03-09</li>
                    <li><i class="fa fa-user"></i> 作者 7att1ce</li>
                    <li>
                        <i class="fa fa-edit"></i> 
                        
                        
                            1142
                        
                        字
                    </li>
                    
                </ul>
            </header>
            <div class="kratos-post-content">
                <div id="expire-alert" class="alert alert-warning hidden" role="alert">
                    本文最后编辑于 <time datetime="1620668221581"></time> 前，其中的内容可能需要更新。
                </div>
                
                <hr />
                <h2 id="1-基础知识"><a href="#1-基础知识" class="headerlink" title="1 基础知识"></a>1 基础知识</h2><h3 id="1-1-渐进符号"><a href="#1-1-渐进符号" class="headerlink" title="1.1 渐进符号"></a>1.1 渐进符号</h3><ul>
<li>如果$\lim\limits_{n\to\infty}\frac{f(n)}{g(n)}$存在并且等于某个常数$c&gt;0$, 那么$f(n)=\Theta(g(n))$</li>
<li>如果$\lim\limits_{n\to\infty}\frac{f(n)}{g(n)}=0$, 那么$f(n)=o(g(n))$</li>
<li>如果$\lim\limits_{n\to\infty}\frac{f(n)}{g(n)}=+\infty$, 那么$f(n)=\omega(g(n))$</li>
<li>假设$f$和$g$是定义域为自然数集合的函数, 若对某个其他的函数$h$, 有$f=O(h)$和$g=O(h)$, 那么$f+g=O(h)$</li>
</ul>
<h3 id="1-2-一些函数性质"><a href="#1-2-一些函数性质" class="headerlink" title="1.2 一些函数性质"></a>1.2 一些函数性质</h3><ul>
<li>$\log n$通常指以二为底的对数</li>
<li>$a^{\log_{b}n}=n^{\log_{b}a}$</li>
<li>$\log_{k}n=\Theta(\log_{l}n)$</li>
<li>对每个$r&gt;1$和每个$d&gt;0$, 有$n^d=o(r^n)$</li>
<li>对每个$b&gt;1$和每个$\alpha&gt;0$, 有$\log_{b}n=o(n^\alpha)$</li>
<li>斯特灵(Stirling)公式$n!=\sqrt{2\pi n}\left(\frac{n}{e}\right)^n\left(1+\Theta\left(\frac{1}{n}\right)\right)$</li>
<li>$n!=o(n^n)$, $n!=\omega(2^n)$, $\log(n!)=\Theta(nlog n)$</li>
<li>取整函数性质<ul>
<li>$x-1&lt;\lfloor x \rfloor\leq x \leq \lceil x \rceil&lt;x+1$</li>
<li>$\lfloor x+n \rfloor=\lfloor x \rfloor+n$, $\lceil x+n \rceil=\lceil x \rceil+n$, 其中$n$为整数</li>
<li>$\lceil \frac{n}{2} \rceil+\lfloor \frac{n}{2} \rfloor=n$, 其中$n$为整数</li>
<li>$\left\lceil \frac{\left\lceil \frac{n}{a} \right\rceil}{b} \right\rceil=\left\lceil \frac{n}{ab} \right\rceil$, $\left\lfloor \frac{\left\lfloor \frac{n}{a} \right\rfloor}{b} \right\rfloor=\left\lfloor \frac{n}{ab} \right\rfloor$, 其中$n$, $a$, $b$为整数</li>
</ul>
</li>
</ul>

            </div>
            
                <div class="kratos-copyright text-center clearfix">
                    <h5>本作品采用 <a rel="license nofollow" target="_blank" href="https://creativecommons.org/licenses/by-sa/4.0/">知识共享署名-相同方式共享 4.0 国际许可协议</a> 进行许可</h5>
                </div>
            
            <footer class="kratos-entry-footer clearfix">
                
                    <div class="post-like-donate text-center clearfix" id="post-like-donate">
                    
                    
                        <a class="share" href="javascript:;"><i class="fa fa-share-alt"></i> 分享</a>
                        <div class="share-wrap" style="display: none;">
    <div class="share-group">
        <a href="javascript:;" class="share-plain qq" onclick="share('qq');" rel="nofollow">
            <div class="icon-wrap">
                <i class="fa fa-qq"></i>
            </div>
        </a>
        <a href="javascript:;" class="share-plain qzone" onclick="share('qzone');" rel="nofollow">
            <div class="icon-wrap">
                <i class="fa fa-star"></i>
            </div>
        </a>
        <a href="javascript:;" class="share-plain weixin pop style-plain" rel="nofollow">
            <div class="icon-wrap">
                <i class="fa fa-weixin"></i>
            </div>
            <div class="share-int">
                <div class="qrcode" id="wechat-qr"></div>
                <p>打开微信“扫一扫”，打开网页后点击屏幕右上角分享按钮</p>
            </div>
        </a>
        <a href="javascript:;" class="share-plain weibo" onclick="share('weibo');" rel="nofollow">
            <div class="icon-wrap">
                <i class="fa fa-weibo"></i>
            </div>
        </a>
        <a href="javascript:;" class="share-plain facebook style-plain" onclick="share('facebook');" rel="nofollow">
            <div class="icon-wrap">
                <i class="fa fa-facebook"></i>
            </div>
        </a>
        <a href="javascript:;" class="share-plain twitter style-plain" onclick="share('twitter');" rel="nofollow">
            <div class="icon-wrap">
                <i class="fa fa-twitter"></i>
            </div>
        </a>
    </div>
    <script type="text/javascript">
        $(()=>{
            new QRCode("wechat-qr", {
                text: "http://7att1ce.github.io/2021/03/09/%E7%AE%97%E6%B3%95%E8%AE%BE%E8%AE%A1%E4%B8%8E%E5%88%86%E6%9E%90/",
                width: 150,
                height: 150,
                correctLevel : QRCode.CorrectLevel.H
            });
        });
        function share(dest) {
            const qqBase        = "https://connect.qq.com/widget/shareqq/index.html?";
            const weiboBase     = "https://service.weibo.com/share/share.php?";
            const qzoneBase     = "https://sns.qzone.qq.com/cgi-bin/qzshare/cgi_qzshare_onekey?";
            const facebookBase  = "https://www.facebook.com/sharer/sharer.php?";
            const twitterBase   = "https://twitter.com/intent/tweet?";
            const hostUrl       = "http://7att1ce.github.io/2021/03/09/%E7%AE%97%E6%B3%95%E8%AE%BE%E8%AE%A1%E4%B8%8E%E5%88%86%E6%9E%90/";
            const title         = "「算法设计与分析」";
            const excerpt       = `1 基础知识1.1 渐进符号
如果$\lim\limits_{n\to\infty}\frac{f(n)}{g(n)}$存在并且等于某个常数$c&gt;0$, 那么$f(n)=\Theta(g(n))$
如果$\lim\limits_...`;
            let _URL;
            switch (dest) {
                case "qq"       : _URL = qqBase+"url="+hostUrl+"&title="+title+"&desc=&summary="+excerpt+"&site=cxpy";     break;
                case "weibo"    : _URL = weiboBase+"url="+hostUrl+"&title="+title+excerpt;                                 break;
                case "qzone"    : _URL = qzoneBase+"url="+hostUrl+"&title="+title+"&desc=&summary="+excerpt+"&site=cxpy";  break;
                case "facebook" : _URL = facebookBase+"u="+hostUrl;                                                        break;
                case "twitter"  : _URL = twitterBase+"text="+title+excerpt+"&url="+hostUrl;                                break;
            }
            window.open(_URL);
        };
    </script>
</div>
                    
                    </div>
                
                <div class="footer-tag clearfix">
                    <div class="pull-left">
                    <i class="fa fa-tags"></i>
                        
                    </div>
                    <div class="pull-date">
                    <span>最后编辑：2021-05-10</span>
                    </div>
                </div>
            </footer>
        </div>
        
            <nav class="navigation post-navigation clearfix" role="navigation">
                
                <div class="nav-previous clearfix">
                    <a title=" 英语话中华复习" href="/2021/01/07/英语话中华复习/">&lt; 上一篇</a>
                </div>
                
                
                <div class="nav-next clearfix">
                    <a title=" GitHub上传方法" href="/2021/03/11/GitHub上传方法/">下一篇 &gt;</a>
                </div>
                
            </nav>
        
        
    </article>
</section>

                
            

<section id="kratos-widget-area" class="col-md-4 hidden-xs hidden-sm">
    <!-- 文章和页面根据splitter来分割，没有的话就从头开始设置为sticky -->
    
    
                <aside id="krw-about" class="widget widget-kratos-about clearfix">
    <div class="photo-background"></div>
    <div class="photo-wrapper clearfix">
        <div class="photo-wrapper-tip text-center">
            <img class="about-photo" src="/images/avatar.webp" />
        </div>
    </div>
    <div class="textwidget">
        <p class="text-center"></p>
    </div>
</aside>
            
                    <div class="sticky-area">
                
                

            
                
            
                
  <aside id="krw-posts" class="widget widget-kratos-posts">
  <h4 class="widget-title"><i class="fa fa-file"></i>最新文章</h4>
  <div class="tab-content">
      <ul class="list-group">
        
        
          
          
            <a class="list-group-item" href="/2021/05/12/%E9%98%85%E8%AF%BB%E7%AC%94%E8%AE%B0/"><i class="fa  fa-book"></i> 阅读笔记</a>
            
          
        
          
          
            <a class="list-group-item" href="/2021/03/15/%E8%AE%A1%E7%AE%97%E6%9C%BA%E7%BB%84%E6%88%90%E5%8E%9F%E7%90%86/"><i class="fa  fa-book"></i> 计算机组成原理</a>
            
          
        
          
          
            <a class="list-group-item" href="/2021/03/15/%E6%AF%9B%E6%A6%82/"><i class="fa  fa-book"></i> 毛概</a>
            
          
        
          
          
            <a class="list-group-item" href="/2021/03/11/GitHub%E4%B8%8A%E4%BC%A0%E6%96%B9%E6%B3%95/"><i class="fa  fa-book"></i> GitHub上传方法</a>
            
          
        
          
          
            <a class="list-group-item" href="/2021/03/09/%E7%AE%97%E6%B3%95%E8%AE%BE%E8%AE%A1%E4%B8%8E%E5%88%86%E6%9E%90/"><i class="fa  fa-book"></i> 算法设计与分析</a>
            
          
        
          
            
          
            
          
            
          
            
      </ul>
  </div>
  </aside>

            
    </div>
</section>
        
        </div>
    </div>
</div>
<footer>
    <div id="footer"  class="ap-lrc"  >
        <div class="kr-tool text-center">
            <div class="tool">
                
                    <div class="box search-box">
                        <a href="/search/">
                            <span class="fa fa-search"></span>
                        </a>
                    </div>
                
                
                    <div class="box theme-box" id="darkmode-switch">
                        <span class="fa fa-adjust"></span>
                    </div>
                
                
            </div>
            <div class="box gotop-box">
                <span class="fa fa-chevron-up"></span>
            </div>
        </div>
        <div class="container">
            <div class="row">
                <div class="col-md-6 col-md-offset-3 footer-list text-center">
                    <ul class="kratos-social-icons">
                        
                        
                        <li><a target="_blank" rel="nofollow" href="https://t.me/CandyUnion"><i class="fa fa-telegram"></i></a></li>
                        
                        
                        
                        <li><a target="_blank" rel="me" href="https://nya.one/@Candinya"><i class="fa fa fa-share-alt-square"></i></a></li>
                        <li><a target="_blank" rel="nofollow" href="https://github.com/Candinya"><i class="fa fa-github"></i></a></li>
                        
                    </ul>
                    <ul class="kratos-copyright">
                        <div>
                            <li>&copy; 2021 7att1ce's blog 版权所有.</li>
                            <li>本站已运行<span id="span_dt">Loading...</span></li>
                        </div>
                        <div>
                            <li>Theme <a href="https://github.com/Candinya/Kratos-Rebirth" target="_blank">Kratos:Rebirth</a></li>
                            <li>Site built with&nbsp;<i class="fa fa-heart throb" style="color:#d43f57"></i>&nbsp;by 7att1ce.</li>
                        </div>
                        <div>
                            <li>Powered by <a href="https://hexo.io" target="_blank" rel="nofollow">Hexo</a></li>
                            <li>Hosted on <a href="https://github.io" target="_blank">Github Pages</a></li>
                        </div>
                        <div>
                            
                            
                        </div>
                    </ul>
                </div>
            </div>
        </div>
    </div>
</footer>
</div>
</div>

        <script defer src="https://cdn.jsdelivr.net/npm/bootstrap@3.3.4/dist/js/bootstrap.min.js"></script>
<script defer src="https://cdn.jsdelivr.net/npm/nprogress@0.2.0/nprogress.js"></script>
<script>const notMobile = (!(navigator.userAgent.match(/(phone|pad|pod|iPhone|iPod|ios|iPad|Android|Mobile|BlackBerry|IEMobile|MQQBrowser|JUC|Fennec|wOSBrowser|BrowserNG|WebOS|Symbian|Windows Phone)/i)));</script>

<script async src="/js/candy.min.js"></script>

    <script defer src="https://cdn.jsdelivr.net/npm/aplayer@1.10.1/dist/APlayer.min.js"></script>
    
    <script defer src="https://cdn.jsdelivr.net/npm/meting@2/dist/Meting.min.js"></script>
    <meting-js
        server="netease"
        type="playlist"
        id="3204190542"
        order="random"
        fixed="true"
    >
    </meting-js>



    <script defer src="https://cdn.jsdelivr.net/gh/fancyapps/fancybox@3.5.7/dist/jquery.fancybox.min.js"></script>

<script defer src="https://cdn.jsdelivr.net/npm/clipboard@2.0.6/dist/clipboard.min.js"></script>
<script defer src="/js/kratosr.min.js"></script>
<script defer src="/js/pjax.min.js"></script>


    <script defer src="/js/kr-dark.min.js"></script>



<!-- Extra support for third-party plguins  -->


    </body>
</html>